package seqlist.oj;

/**
 * @Author: yuisama
 * @Date: 2019/12/6 17:22
 * @Description:合并两个有序链表-引入额外空间，不影响原先两个链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class Solution21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }else {
            // l1与l2均不为空
            ListNode l = l1;
            ListNode r = l2;
            ListNode dummyHead = new ListNode(-1);
            ListNode temp = dummyHead;
            // 两个链表均还有元素
            while (l != null && r != null) {
                if (l.val < r.val) {
                    temp = link(l.val,temp);
                    l = l.next;
                }else {
                    temp = link(r.val,temp);
                    r = r.next;
                }
            }
            while (l != null) {
                temp = link(l.val,temp);
                l = l.next;
            }
            while (r != null) {
                temp = link(r.val,temp);
                r = r.next;
            }
            return dummyHead.next;
        }
    }

    private ListNode link(int val,ListNode temp) {
        ListNode node = new ListNode(val);
        temp.next = node;
        temp = node;
        return temp;
    }
}
